package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/31 14:40
 **/
public class Day46_2_Offer24_ReverseList {
    // 头插
    class Solution1 {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode dummyHead = new ListNode(-1);
            while(head != null){
                ListNode cur = new ListNode(head.val);
                cur.next = dummyHead.next;
                dummyHead.next = cur;
                head = head.next;
            }
            return dummyHead.next;
        }
    }
    // 三指针
    class Solution2 {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode pre = head;
            ListNode cur = head.next;
            ListNode next = cur.next;
            while(next != null){
                cur.next = pre;

                pre = cur;
                cur = next;
                next = next.next;
            }
            // 最后还有一个值
            cur.next = pre;
            head.next = null;
            return cur;
        }
    }
    // 递归
    class Solution {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode second = head.next;
            ListNode newHead = reverseList(head.next);

            second.next = head;
            head.next = null;
            return newHead;
        }
    }
}